package leetcode_81_100;

import com.sun.javafx.scene.input.InputEventUtils;
import utils.ListNode;

public class partition_86 {
    /**
     * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔
     * 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     *
     * 你应当 保留 两个分区中每个节点的初始相对位置
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        /**
         * 想法是拼接两个链表，so easy
         * 100% 0ms
         */
        ListNode root1=new ListNode();
        ListNode r1=root1;
        ListNode root2=new ListNode();
        ListNode r2=root2;
        while (head!=null){
            if(head.val<x){
                r1.next=head;
                r1=r1.next;
            } else{
                r2.next = head;
                r2 = r2.next;
            }
            head=head.next;
        }
        r2.next= null; //排除最后一个节点非尾节点时，造成循环链表
        r1.next=root2.next; //进行拼接
        return root1.next;
    }
}
